1. Field
Embodiments of the invention relate to the field of networking and more specifically, but not exclusively, to a hierarchical packet scheduler that uses hole-filling and multiple packet buffering.
2. Background Information
Networks provide the infrastructure for many forms of communication. LANs (Local Area Network), WANs (Wide Area Network), MANs (Metropolitan Area Network), and the Internet are common networks. Packets sent on networks are often handled by various network devices such as bridges, hubs, switches, and routers.
Typically, a packet flow in a network is routed between routers until the packets reach their destination. At any time, there may be many packet flows traversing the network between sources and destinations. When packets enter a network device, logic within the network device schedules the packets for forwarding onto their destinations.
As bit rates across networks increase, the speed of packet flow through network devices becomes a key to transmission speed between source and destination. When a network device processes multiple packet flows at the same time, packets are scheduled to maximize the rate of flow through the network device. Many current scheduling designs fail to maintain packet scheduling at the line rates of network devices.